package _stack_queue

import org.junit.Assert
import org.junit.Test
import java.util.*

/**
 * 225. 用队列实现栈
 * https://leetcode.cn/problems/implement-stack-using-queues/description/
 * https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html
 *
 * 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
 *
 * 实现 MyStack 类：
 *
 * void push(int x) 将元素 x 压入栈顶。
 * int pop() 移除并返回栈顶元素。
 * int top() 返回栈顶元素。
 * boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 *
 * MyStack myStack = new MyStack();
 * myStack.push(1);
 * myStack.push(2);
 * myStack.top(); // 返回 2
 * myStack.pop(); // 返回 2
 * myStack.empty(); // 返回 False
 *
 */
class leetcode_225 {
    @Test
    fun test_1() {
        val myStack: MyStack = MyStack();
        myStack.push(1);
        myStack.push(2);
        val actual = myStack.top(); // 返回 2
        Assert.assertEquals(2, actual)

        val actual2 = myStack.pop(); // 返回 2
        Assert.assertEquals(2, actual2)

        val actual3 = myStack.empty(); // 返回 False
        Assert.assertEquals(false, actual3)
    }

    private class MyStack() {
        var q1: LinkedList<Int> = LinkedList<Int>();
        var q2: LinkedList<Int> = LinkedList<Int>();

        fun push(x: Int) {
            q1.offer(x)
        }

        fun pop(): Int {
            val size: Int = q1.size
            for (i in 1..size - 1) { // [0, size-1]
                val num: Int = q1.poll()
                q2.offer(num)
            }
            val result = q1.removeFirst()

            // swipe
            val temp: LinkedList<Int> = q1
            q1 = q2
            q2 = temp
            return result
        }

        fun top(): Int {
//            return q1.peekLast()
            val result = pop();
            q1.offer(result)
            return result
        }

        fun empty(): Boolean {
            return q1.isEmpty()
        }
    }
}